package subject.tengxun.middle.easy;

import java.util.HashMap;
import java.util.Map;

/**
 * 功能：给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
 * 作者：yedou
 * 日期：2025/6/23
 */
public class singleNumber {
    public static void main(String[] args) {
        int[] nums = {2, 2, 1};

        System.out.println(method1(nums));

        singleNumber singleNumber = new singleNumber();
        System.out.println(singleNumber.method2(nums));

    }

    /**
     * 利用哈希表值为初始值的那个键值就是结果
     *
     * @param nums
     * @return
     */
    public static int method1(int[] nums) {
        // 新建一个哈希表
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            // 判断键值是否存在
            if (!map.containsKey(num)) {
                // 如果不存在就存入{num: 0}
                map.put(num, 0);
            } else {
                // 如果存在就把键值对应的值加1
                map.put(num, map.get(num) + 1);
            }

        }
//        System.out.println(map);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
//
//            System.out.println(entry.getValue());
            if (entry.getValue() == 0) {
                // 选择那个值等于0的count就是
                return entry.getKey();
            }
        }
        return -1;
    }

    /**
     * 利用相同数字异或为0,不同数字异或为1,保留的那个数字就是结果
     *
     * @param nums
     * @return
     */
    public int method2(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result = num ^ result;
        }
        return result;
    }
}